状压DP Codeforces 1234F

本文最后更新于：2024年9月13日 早上

题目描述

You are given a string s consisting only of first 20 lowercase Latin letters (‘a’, ‘b’, …, ‘t’).
Recall that the substring of the string s is the string slsl+1…sr. For example, the substrings of “codeforces” are “code”, “force”, “f”, “for”, but not “coder” and “top”.
You can perform the following operation no more than once: choose some substring and reverse it (i.e. the string becomes ).
Your goal is to maximize the length of the maximum substring of s consisting of distinct (i.e. unique) characters.
The string consists of distinct characters if no character in this string appears more than once. For example, strings “abcde”, “arctg” and “minecraft” consist of distinct characters but strings “codeforces”, “abacaba” do not consist of distinct characters.

输入格式 Input Format

  • The only line of the input contains one string s consisting of no more than characters ‘a’, ‘b’, …, ‘t’ (first 20 lowercase Latin letters).

输出格式 Output Format

  • Print one integer — the maximum possible length of the maximum substring of s consisting of distinct characters after reversing no more than one its substring.

输入：

abcdeefc

输出：

6

中文题意

你有一个字符串，里面的字符全是0~20(a~t)以内的小写字母，你可以通过旋转一段区间的方式把它变成一个新的字符串，我们这里对旋转的定义是将一段区间的 变成 。问你只能旋转一次，使得新字符串中的不含相同字符的合法子串(这里对合法子串的定义是连续的一段区间串)最长，输出最长的长度。

想法

yxh学长给新生拉的div3水题. . .竟然没想起来咋搞
由于可以通过旋转操作把一段连续的区间和另一段拼合，呢么我们可以简化一下模型，即问源字符串两段没有重合字符的合法子串的和的最长长度。
由于数据范围给的很小，0~20这就是写在脑门子上的状压。
不过当时在测试的时候想的是通过来记录第i个数往后推j个数的字符占有状态。但是想不出状态转移方程，便不了了之。
正解是通过来表示一段合法字符串字母占有状态为i时，在原串中可以找的到的字串的最长长度。
这种记录方法很妙，因为我们实际上再找一个状态i的子串和其他与它不冲突的子串时，一些不冲突的子串是目标不冲突子串的子集，枚举他们是没有比较意义的。因此我们直接将每一个子串都向以它为子集的字串提交贡献，假如可以提供贡献就会被以它为子集的字串记录(怎么有种树的感觉，儿子向父亲提交状态)。因此我们对状态为i的串，我们可以通过它的互补串来快速得出它在原串中最大互补的子串。最后答案就是每种状态i和其互补态的长度和的最大值。
感觉这个状态转移的很妙，这是一种类似状态树的玩意，父集合可以代表所有子状态中最优的，然后通过父集合再向父父集合传递贡献从而降低了时间复杂度。
以及学了一些状压技巧。
具体见代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<bits/stdc++.h>
using namespace std;
long long n,a[1000100],b[1100100]={};
long long c[30],maxn,ans=-1;
char ch1[1000100];
int main()
{
    //freopen("a.in","r",stdin);
    //freopen("a.out","w",stdout);
    scanf("%s",ch1+1);
    n=strlen(ch1+1);
    c[0]=1;maxn=1;for(int i=1;i<=20;i++)c[i]=c[i-1]<<1,maxn<<=1;
    for(int i=1,nowzhuang,j;i<=n;i++)
        for(j=0,nowzhuang=0;j<=20&&i+j<=n;j++)
        {
            if((c[ch1[i+j]-'a']&nowzhuang))break;
            nowzhuang|=c[ch1[i+j]-'a'];
            b[nowzhuang]=j+1;
            //cout<<nowzhuang<<' ';
        }//cout<<endl;
    for(int i=1;i<maxn;i++)
        for(int j=0;j<=20;j++)
            if(i&c[j])
                b[i]=max(b[i],b[i^c[j]]);
    //cout<<maxn<<endl;
    for(int i=1;i<maxn;i++)
    {
        //cout<<i<<' ';
        //if(b[i]+b[maxn-i-1]>ans)cout<<i<<' '<<b[i]<<endl;
        ans=max(ans,b[i]+b[maxn-i-1]);
    }//cout<<endl;
    cout<<ans<<endl;
    return 0;
}